Problem:
There are now a set of items where each item has its value and weight.  You have a knapsack and hope to put in as many valuable items as possible. However the knapsack’s capacity is limited to some weight W that the total weight of selected items should not exceed W. The goal is to select a collection of items achieving the maximum total value while satisfying the capacity restriction.
This problem in general is called the knapsack problem and it has many variations. In the fractional setting here, each item could be arbitrarily divided so that only a fraction of the item is taken. For example, suppose item A has weight 4 and value 10. Then a 1/2 fraction of item A will occupy 2 weight and has value 5.

Solution:
A natural greedy strategy is to prefer high value low weight items. And in fact this greedy heuristic is optimal in our fractional setting. First let’s define density for each item:
The density of an item is the item’s value divided by its weight.

Algorithm

Keep selecting the highest density item among all the unselected items, until the total weight exceeds W or there is no item left. Note that only the last selected item may be fractional.

Correctness:
Compared with the greedy algorithm’s solution, any other different combination of items could be viewed as swapping knapsack capacity to lower density items which will decrease the total value. So it is easy to see that the greedy solution is optimal.

Time Complexity:
To implement the algorithm a sorting is needed to arrange the items’ densities in order. And the total time complexity is dominated by this sorting phase and is thus O(n log n).

Pseudo Code

Fractional-knapsack

Input: an array item[1..n] with properties v (value) and w (weight)
           knapsack capacity W
Output: a set S of items with property f (fraction)

    for i = 1 to n
        d(item[i]) = w(item[i]) / v(item[i])
    descending sort item[] according to d (densities)
    V = 0
    totalWeight = 0
        for i = 1 to n
            if (totalWeight  ≥ W)
                break
            if(item[i]) = min { 1, (W-totalWeight) / w(item[i]) }
            S = S ∪ { item[i] }
            totalWeight += w(item[i])
    return S
		

Other references:

[1] http://en.wikipedia.org/wiki/Huffman_coding
[2] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, Second Edition. The MIT Press, Massachusetts, 2001
[3] Dasgupta, S., Papadimitriou, C. H., and Vazirani, U. V. Algorithms. McGraw-Hill Higher Education, 2006.